package org.xiaojinlong.exam;

import java.util.Arrays;

/**
 * @author Jin Long
 * 2015/8/23
 * 由于题目保证所有的数字不是出现两次就是三次，因此最直接的方法就是直接计算数字出现的次数
 * 可以先用系统的排序，复杂度为nlogn
 * 排序过后直接扫描数组，此时相同数字都处于相邻位置，
 * 可以方便的计算出现次数，发现次数为3的就可以停止扫描了
 */
public class New {

    static int findTriple(int a[]) {
        Arrays.sort(a);
        int times = 1; // 记录数字出现次数
        for (int i = 1; i < a.length; i++) {
            if (a[i] == a[i-1]) times += 1;
            else {
                if (times == 3) // 如果找到出现次数为3的数字则停止
                    return a[i-1];
                times = 1;
            }
        }
        if (times == 3) return a[a.length-1]; // 边界情况
        return 0;
    }

    public static void main(String[] args) {
        int[] a = {88, 459, 5262, 88, -17, 677, 88, 667, -17, 459, 5262};
        assert findTriple(a) == 88;
    }
}


